package com.autumn.annotations.leetcode.leet;

import com.autumn.annotations.leetcode.basic.TreeNode;

/**
 * ClassName: IsValidBST
 *
 * @Description:
 * @Author: wangqiuyang
 * @Date: 2022/1/19 8:10 下午
 * History:
 * <author>          <time>          <version>          <desc>
 * wangqiuyang    2022/1/19 8:10 下午   @Version 1.0        描述
 */
public class IsValidBST {

    /*
        校验二叉搜索树是否成立
     */
    public static boolean isValidBST(TreeNode root) {

        if (root == null) {
            return true;
        }

        // 检查左节点所有的值是否比根结点小 && 检查右节点的所有值是否比根结点大
        if (!(check(root.left , true , root.val) && check(root.right , false , root.val))){
            return false;
        }

        // 遍历左节点和右节点
        return isValidBST(root.left) && isValidBST(root.right);
    }


    public static boolean check(TreeNode root , boolean isLeft , int val) {
        if (root == null) {
            return true;
        }

        if (isLeft && root.val >= val || !isLeft && root.val <= val) {
            return false;
        }
        return check(root.left , isLeft , val) && check(root.right , isLeft , val);
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(5);
//        TreeNode leaf1 = new TreeNode(1);
//        TreeNode leaf2 = new TreeNode(4);
//        TreeNode leaf3 = new TreeNode(3);
//        TreeNode leaf4 = new TreeNode(6);
//        root.left = leaf1;
//        root.right = leaf2;
//
//        leaf2.left = leaf3;
//        leaf2.right = leaf4;

        TreeNode root = new TreeNode(2);
        TreeNode leaf1 = new TreeNode(1);
        TreeNode leaf2 = new TreeNode(3);
        root.left = leaf1;
        root.right = leaf2;

        boolean validBST = isValidBST(root);
        System.out.println(validBST);
    }
}
